iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 5
0
自我挑戰組

[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ系列 第 5

[LeetCode with JavaScript] Day 5: String to Integer (atoi)

  • 分享至 

  • xImage
  •  

觀前提醒:

  1. 我預設大家已經先思考並分析過題目,沒啥想法才開始 google 找解題靈感。若無,建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法
  2. 承上,既然已經有思考過了,那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了,那我可能解題想法 & 心得的部分就不會寫太多,免得干擾你的思考。
  3. 所有解法都是已經取得系統的 Accepted,但或許不是最優解法,請多包涵。
  4. 若對於解法不太懂,可以嘗試用 Chrome 的 debugger 來試跑看看 (教學文)
  5. 最後,歡迎在下面留言指教~教學相長才會進步歐~/images/emoticon/emoticon41.gif

題目

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

  • Only the space character ' ' is considered as whitespace character.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

Input: "42"
Output: 42

Example 2:

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.

解題想法

起初看到這題,覺得他的通過率低的很可怕。但其實慢慢的一邊改一邊做,經過不斷地 Trial & Error,最後還是解得出來。詳情請參考我在CODE裡面的註解~

CODE

/**
 * @param {string} str
 * @return {number}
 */
var myAtoi = function (str) {
  // 檢查 The first non-whitespace character is not a numerical digit or a + /- sign.
  // remove whitespace from beginning of string
  str = str.trimLeft();
  let re = /[\d+-]/;
  // if first character is not +,- or a digit
  if (!re.test(str[0])) return 0;
  // 僅保留數字部分
  let numOfStr = "";
  for (let i = 0; i < str.length; i++) {
    if (re.test(str[i])) {
      numOfStr += str[i];
    } else {
      break;
    }
  }
  // 若右方有特殊符號,包含符號在內一並刪除。 ex. '-5-' -> '-5'
  // 解法:建立 數字的正規表達式,然後利用 while 迴圈 + RegExp.test 一一確認整包字串,從numOfStr[1] 開始,哪個字元不是數字,確認他的位置!
  let numReg = /\d/;
  let endOfNum = 1;
  while (endOfNum < numOfStr.length && numReg.test(numOfStr[endOfNum])) {
    endOfNum++;
  }
  // 截出開頭的數字字串, ex. '-5-' -> '-5'
  numOfStr = numOfStr.substring(0, endOfNum);

  // 開始把字串轉換成數字,並注意edge case。
  let ansNum = Number(numOfStr);
  // 處理 example 4 的情況
  if (Number.isNaN(ansNum)) {
    return 0;
  }
  // 處理 example 5 的情況
  else if (ansNum > 2 ** 31 - 1) {
    return 2 ** 31 - 1;
  } else if (ansNum < -(2 ** 31)) {
    return (-2) ** 31;
  } else {
    return ansNum;
  }
};

心得

大家跟著我的解法,一步步跑應該沒有啥大礙,只是這題目真D一堆小坑,example 裡面的 Explanation 也一堆毛,一度想破頭>_<。但,我不放棄,因為看到 “X / 1079 test cases passed”,那個 X 的數量不斷上升,真的好舒服
對新手來說,其中以下有兩小一大 prerequisite,也算是個不小的坑,建議直接按下面的文章連結,方便大家操作~


那麼今天先這樣,我們明天見~/images/emoticon/emoticon29.gif


上一篇
[LeetCode with JavaScript] Day 4: Reverse Integer
下一篇
[LeetCode with JavaScript] Day 6: Longest Common Prefix
系列文
[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言